package mySort;
//归并排序非递归法
public class MergeSortNor {
    public void mergeSort(int[] arr) {
        int gap = 1;
        while (gap < arr.length) {
            //一组一组比较
            for (int i = 0; i < arr.length; i += 2 * gap) {
                int left = i;
                int mid = i + gap - 1;
                if (mid >= arr.length) {
                    mid = arr.length - 1;
                }
                int right = mid + gap;
                if (right >= arr.length) {
                    right = arr.length - 1;
                }
                merge(arr, left, mid, right);
            }
            gap *= 2;
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int start1 = left;
        int start2 = mid + 1;
        int[] tmpArr = new int[right - left + 1];
        int index = 0;

        while (start1 <= mid && start2 <= right) {
            if (arr[start1] < arr[start2]) {
                tmpArr[index++] = arr[start1];
            } else {
                tmpArr[index++] = arr[start2++];
            }
        }
        while (start1 <= mid) {
            tmpArr[index++] = arr[start1++];
        }
        while (start2 <= right) {
            tmpArr[index++] = arr[start2++];
        }

        for (int i = 0; i < index; i++) {
            arr[left + i] = tmpArr[i];
        }
    }
}
